package com.jia;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-10 19:10
 */
public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int count = 1;
        int N = 100;
        int[] v = new int[n+1];
        int[] w = new int[m+1];
        while(count <= n) {
            v[count] = scanner.nextInt();
            w[count] = scanner.nextInt();
            ++count;
        }
        int[] dp = new int[m+1];
        for(int i = 1; i <= n; i++) {

            for(int j = v[i]; j <= m; j++) {
//                f[k] = Math.max(f[k], f[k-v[j]] + w[j]);
                dp[j] = Math.max(dp[j],dp[j-v[i]] + w[i]);
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[m]);
    }
}
